/*
 * medianOfMedian.cpp
 *
 *  Created on: Sep 11, 2012
 *      Author: jeffrey
 */

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class MedianOfMedians {
public:
	static int selectK(int a[], int len, int k) {
		return selectK(a, 0, len - 1, k);
	}
private:
	static int swap(int a[], int i, int j) {
		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;
	}
	static int selectK(int a[], int s, int e, int k) {
		if (e - s < 10) { // if size is small, just sort
			vector<int> vs(a + s, a + e + 1);
			std::sort(vs.begin(), vs.end());
			return vs[k - 1];
		}
		int medLen = (e - s + 1) / 5;
		int *medians = new int[medLen];
		// get medians of 5-num groups
		for (int i = 0; i < medLen; i++) {
			medians[i] = selectK(a, s + i * 5, s + i * 5 + 4, 3);
		}
		// get median of medians
		int m = selectK(medians, 0, medLen - 1, medLen / 2);
		delete[] medians;
		int tmp = s;
		for (int i = s; i <= e; i++) {
			if (a[i] < m)
				swap(a, tmp++, i);
		}
		int less = tmp - s;
		tmp = e;
		for (int i = e; i >= s; i--) {
			if (a[i] > m)
				swap(a, tmp--, i);
		}
		int great = tmp - s + 1;
		if (k <= less)
			return selectK(a, s, s+less - 1, k);
		else if (k > great)
			return selectK(a, s+great, e, k - great);
		else
			return m;
	}
};
//int main() {
//	for (int i = 1; i <= 39; i++) {
//		int a[] = { 2, 5, 3, 8, -19, 8, 9, -3, -15, 34, 26, 7, 9,2, 5, 3, 8, -19, 8, 9, -3, -15, 34, 26, 7, 9,2, 5, 3, 8, -19, 8, 9, -3, -15, 34, 26, 7, 9,2, 5, 3, 8, -19, 8, 9, -3, -15, 34, 26, 7, 9 };
//		cout << MedianOfMedians::selectK(a, 13, i) << endl;
//	}
//}

